package jjn.round2;

/**
 * @author Jiang Jining
 * @since 2023-05-12 23:37
 */
public class Offer12_PathExistence {
    
    public boolean exist(char[][] board, String word) {
        int height = board.length;
        int width = board[0].length;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                boolean dfs = dfs(board, i, j, 0, word);
                if (dfs) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, int i, int j, int k, String word) {
        int height = board.length;
        int width = board[0].length;
        if (i < 0 || i >= height || j < 0 || j >= width) {
            return false;
        }
        if (word.charAt(k) != board[i][j]) {
            return false;
        }
        if (k == word.length() - 1) {
            return true;
        }
        board[i][j] = '\0';
        boolean res = dfs(board, i + 1, j, k + 1, word) || dfs(board, i, j + 1, k + 1, word)
                || dfs(board, i - 1, j, k + 1, word) || dfs(board, i, j - 1, k + 1, word);
        board[i][j] = word.charAt(k);
        return res;
    }
}
